Cardinality of a Set
The cardinality of a set is a way of quantifying and comparing the "size" of sets, even in the case of infinite sets.
In the case of finite sets, we can identify the size of \(S\) by the number of elements it has.
Let \(S\) be a finite set, thus there is a bijection \(S \to \{1, \dots, n\}\) and we say the cardinality of \(S\) is given by
This allows us to compare the size of sets by using the canonical ordering on the natural numbers.
This however does not generalise for infinite sets. As such, consider an alternative approach to determining if two sets have the same size. Namely, remove one element form each set at the same time, and continue until either set runs out of elements. Whichever set runs out first has fewer elements. This idea of pairing elements from each set together motivates the general definition of the cardinality of a set.
Reading \(|A|\) as the cardinality of \(A\), we have that
- \(|A| = |B|\) if and only if there is a bijection \(A \to B\).
- \(|A| \leq |B|\) if and only if there is an injection \(A \to B\).
- \(|A| < |B|\) if and only if there is an injection \(A \to B\) but no bijection \(A \to B\).
This notation hints at the following being true
and furthermore that exactly one of the following holds
These results are due to Schroder-Bernstein theorem and cardinal trichotomy, the latter of which is equivalent to the axiom of choice.